/*
 * @FilePath: \undefinedc:\Users\sxjct\.leetcode\347.前-k-个高频元素.cpp
 * @Brief: 
 * @Version: 1.0
 * @Date: 2021-03-29 10:11:09
 * @Author: tianyiyi
 * @Copyright: Copyright@tianyiyi
 * @LastEditors: Mr.Tian
 * @LastEditTime: 2021-03-29 10:53:33
 */
/*
 * @lc app=leetcode.cn id=347 lang=cpp
 *
 * [347] 前 K 个高频元素
 */

// @lc code=start
class Solution {
    
public:
    // 求前k大元素，那么就使用小根堆，始终维持堆中元素为k个即可
    vector<int> topKFrequent(vector<int>& nums, int k) {
        using E = std::pair<int,int>;
        priority_queue<E,vector<E>,std::greater<E>> que;
        unordered_map<int,int> map;
        for(auto i : nums)
        {
            map[i]++;
        }
        for(auto i : map)
        {
            auto pair = make_pair(i.first,i.second);
            if(que.size() == k)
            {
                if(pair < que.top())
                    continue;
                que.pop();
            }
            que.push(std::move(pair));
        }

        vector<int> res;
        while(!que.empty())
        {
            res.insert(res.begin(),que.top().first);
            que.pop();
        }
        return res;



    }
};
// @lc code=end

